One of the most important processes in digital signal processing is a fast Fourier transform (hereinafter, called “FFT”). For example, a frequency domain equalization (FDE) technique has been known as a technique to compensate waveform distortion during signal transmission in wireless or wired communications. In the frequency domain equalization (FDE), first, time-domain signal data are converted into frequency-domain data by the fast Fourier transform, and then a filter process is performed for equalization. The filtered data are reconverted into time-domain signal data by an inverse fast Fourier transform (hereinafter, called “IFFT”), by which the waveform distortion in the original time-domain signals is compensated. Hereinafter, if FFT and IFFT are not distinguished, they are denoted by “FFT/IFFT”.
A “butterfly computation” is generally used in the FFT/IFFT processing. An FFT device using the butterfly computation is described in Patent Literature 1, for example. Patent Literature 1 also describes an after-mentioned “twiddle multiplication”, that is, a multiplication using a twiddle factor.
As an efficient FFT/IFFT processing method, the Cooley-Tukey butterfly computation is well known which is described in Non Patent Literature 1, for example. However, the Cooley-Tukey FFT/IFFT with a large number of points requires a complex circuit. Hence, the FFT/IFFT processing is performed which is decomposed into two smaller FFTs/IFFTs by using the Prime Factor method described in Non Patent Literature 2, for example.
FIG. 19 shows a dataflow 500 of a 64-point FFT which is decomposed into two-stage radix-8 butterfly processes by utilizing the Prime Factor method, for example. The dataflow 500 includes a data sorting process 501, radix-8 butterfly computation processes performed sixteen times in total which consist of butterfly computation processes 502 and 503, and a twiddle multiplication process 504.
In the dataflow shown in FIG. 19, the inputted time-domain data x(n) (n=0, 1, . . . , 63) are Fourier-transformed into frequency-domain signals X(k) (k=0, 1, . . . , 63) through the FFT processing. The illustration of the dataflow in FIG. 19 is partly omitted. The dataflow of IFFT processing is basically the same as that shown in FIG. 19.
Implementing the whole dataflow shown in FIG. 19 requires a huge circuit in size. Therefore, a method is generally used for implementing the whole FFT process by using a circuit implementing a part of the dataflow process repetitively depending on the necessary processing performance.
For example, in the dataflow shown in FIG. 19, if an FFT device is made as a physical circuit which performs the FFT processing on eight pieces of data in parallel (hereinafter, called “in 8-data parallel” for short), the repetitive processing with eight times in total can achieve the 64-point FFT processing.
The repetitive processing with eight times is to perform in sequence a processing corresponding to each of partial dataflows 505a to 505h performed on eight pieces of data, as described in more detail below. That is to say, first, a process corresponding to the partial dataflow 505a is performed; secondly, a process corresponding to the partial dataflow 505b, and thirdly, a process corresponding to the partial dataflow 505c (not shown) is performed. Similarly, subsequent processes are performed in sequence until a process corresponding to the eighth partial dataflow 505h. These processes achieve the 64-point FFT processing.
In the butterfly computation, the data arranged in a sequential order are read according to the order following a predetermined rule and processed. Hence, it is necessary in the butterfly computation to rearrange data, for which a random access memory (RAM) is used. An FFT device is described in Patent Literature 2, for example, in which data are rearranged using a RAM in the butterfly computation.
With regard to an FFT computation device with reduced memory usage, a speed-up technique through parallel processing in the butterfly computation is described in Patent Literature 3, for example.